{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "标准（C17 §7.22）只规定了语义：`malloc` 负责从自由存储区（heap）获取至少指定字节数的内存，失败返回 `NULL`；`free` 负责释放由 `malloc` 系列函数获取的内存。**标准并未规定具体实现方式**，因而底层机制依赖于运行时库与操作系统。本节以 Linux/glibc（`ptmalloc2`）为主要参考，辅以其他典型实现（`dlmalloc`、`jemalloc`、`tcmalloc` 等）的共性特征，来解析其工作流程。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 外层架构：用户态分配器与内核接口\n",
    "\n",
    "1. **应用层调用 `malloc`**\n",
    "   - 运行时库提供的分配器（如 glibc 的 `ptmalloc2`）接到请求。\n",
    "   - 分配器管理一套用户空间内存池（堆），用于满足频繁的小块请求。\n",
    "2. **堆内存补充**\n",
    "   - 当现有堆空间不足时，分配器向操作系统请求更多内存：\n",
    "     - 早期传统接口：`sbrk`/`brk` 调整进程数据段（heap）末尾指针。\n",
    "     - 现代实现：对大块请求或多线程场景会直接使用 `mmap` 映射新的匿名内存区域，以减少碎片、支持独立释放。\n",
    "3. **回收内存**\n",
    "   - `free` 将块标记为可用，尝试与相邻空闲块合并以缓解碎片。\n",
    "   - 某些实现可能将整段内存（如大块 `mmap` 区域）归还给内核，通过 `munmap` 或 `madvise`。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 典型分配器内部结构"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 块（chunk）布局\n",
    "\n",
    "\n",
    "```asciidoc\n",
    "+-------------+-----------------+-------------+\n",
    "| chunk header| user payload ... | padding ...|\n",
    "+-------------+-----------------+-------------+\n",
    "```\n",
    "\n",
    "- **Header** 保存元数据：\n",
    "  - 块大小（含对齐和标志位，如“当前块是否在使用”“前一块是否空闲”等）。\n",
    "  - 某些实现（如 `dlmalloc`）在尾部（footer）冗余记录块大小，便于与前一块合并。\n",
    "- **Payload** 返回给用户的指针指向此区域起始处。\n",
    "- **对齐**：通常按 `sizeof(void*)` 或更高（如 16 字节）对齐。\n",
    "- **额外信息**：针对安全检测（如 glibc 的 cookies、tcache key）或调试（如 Electric Fence）会在头尾加入保护区域。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 空闲链表（bins）与分级\n",
    "\n",
    "- **分级策略**：依据空闲块大小划分多个 bin（fast bins、small bins、large bins）。\n",
    "- **链表结构**：双向循环链表，或基于树结构（大块）。\n",
    "- **绕过全局锁的优化**：如 glibc 2.26 起引入每线程缓存（tcache），jemalloc/tcmalloc 使用 per-thread/per-CPU caches 减少锁竞争。\n",
    "- **内存碎片处理**：通过合并邻接空闲块（coalescing）以及分裂大块（splitting）应对外部碎片。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# `malloc` 流程（以 glibc `ptmalloc2` 为例）\n",
    "\n",
    "1. **尺寸调整**\n",
    "   - 将用户请求大小 `n` 转换为满足对齐与内部需求的块大小：`request2size(n)`。\n",
    "2. **尝试从快速缓存获取**\n",
    "   - tcache（thread cache）或 fast bins 中存在对应大小的空闲块时，直接弹出并返回。\n",
    "3. **从合适的 bin 中获取**\n",
    "   - 小块：从 `small bins` 中取出最合适块；若块稍大，会拆分后返回一部分。\n",
    "   - 大块：使用 `large bins`（通常为树结构）寻找最小满足块。\n",
    "4. **寻找不到则向系统请求**\n",
    "   - 调用 `sysmalloc`：\n",
    "     - 首选扩展顶端 chunk（top chunk），若不足则通过 `mmap`（大块）或 `sbrk`（小块）获取新内存。\n",
    "   - 将新得到的内存加入管理结构后，再次分配。\n",
    "5. **返回用户指针**\n",
    "   - 将 chunk header 之后的地址作为结果返回。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# `free` 流程\n",
    "\n",
    "1. **验证指针**\n",
    "   - 检查指针是否为 `NULL`（忽略），否则进行基本的完整性检查（如对应块是否标记为 in-use）。\n",
    "   - glibc 在调试模式或启用了 `MALLOC_CHECK_` 时进行更多校验（双重释放、越界写检测）。\n",
    "2. **获取 chunk**\n",
    "   - 通过指针回退到 `chunk header` 位置。\n",
    "3. **合并（coalescing）**\n",
    "   - 检查前后相邻块是否空闲，若空闲则将它们合并成更大的块，减小碎片。\n",
    "4. **归入对应 bin**\n",
    "   - 小块：插入 fast bin/small bin。\n",
    "   - 大块或合并后大块：可能归入 unsorted bin 再散布到合适 bin。\n",
    "   - tcache（若启用）：优先放入线程本地缓存，缓存溢出后再转给全局 bins。\n",
    "5. **可能的内存归还**\n",
    "   - 如果释放的块位于堆顶或为独立 `mmap` 区域，分配器可能调用 `munmap` 归还给内核（取决于策略和阈值）。\n",
    "   - 常见策略保证频繁使用的容量保留在用户态，以减少系统调用开销。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 其他实现要点对比\n",
    "\n",
    "| 实现                 | 主要特点                                                     |\n",
    "| -------------------- | ------------------------------------------------------------ |\n",
    "| `ptmalloc2`（glibc） | 源自 `dlmalloc`，采用 arena + bins + tcache；支持多线程 arena，减少锁竞争。 |\n",
    "| `jemalloc`           | 广泛用于 FreeBSD、Firefox 等；基于 size-class、per-thread cache、高效对齐和碎片管理。 |\n",
    "| `tcmalloc`（Google） | 关注多线程性能，采用 thread cache + central free list + span allocator。 |\n",
    "| `dlmalloc`           | 经典设计，影响多数后续实现；单线程场景表现良好。             |\n",
    "| `musl` malloc        | 设计较简洁，采用分段结构与多种 bin 配置，兼顾小体积和稳定性。 |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 关键限制与安全注意\n",
    "\n",
    "1. **指针合法性**：`free` 的参数必须是此前 `malloc`、`calloc`、`realloc` 返回的指针，且尚未被释放或修改。否则行为未定义（常见问题：double free、wild pointer）。\n",
    "2. **内存越界写**：若写越界破坏 chunk 元数据，会导致崩溃或可利用的堆漏洞（如 unlink attack，尽管现代实现加入安全检查，但仍需谨慎）。\n",
    "3. **线程安全**：标准规定 `malloc/free` 线程安全，但在同一运行时上可能存在全局锁争用瓶颈；现代实现通过多 arena 或线程缓存缓解。\n",
    "4. **对齐**：若需特定对齐（如 SIMD），应使用 `aligned_alloc`/`posix_memalign`（C11 `<stdalign.h>` 提供 `_Alignof` 获取对齐要求）。\n",
    "5. **内存泄漏与调试**：工具（`valgrind`, `AddressSanitizer`, `malloc_stats`，glibc 的 `MALLOC_TRACE` 等）可辅助检测。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 总结\n",
    "\n",
    "- **`malloc`/`free` 本质**：用户态内存管理器维护的堆块分配与回收机制，必要时通过 `sbrk/mmap` 与操作系统交互。\n",
    "- **运行效率依赖实现**：不同 libc/allocator 为平衡速度、内存碎片、多线程表现设计了复杂的数据结构（空闲链表、缓存、多 arena 等）。\n",
    "- **安全与正确性**：严格遵守成对使用约束（`malloc` 对 `free`），不要越界访问，注意线程环境下的性能和安全调试工具的使用。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "name": "C++17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
